We now turn to the payload description process.
We devised a simple, assembly-like, regular language for encoding our ROP payloads.  It was intended that this language be our analogue to Schwartz, et. al.'s \textit{QooL}, a context-free language performing roughly the same function.  For the sake of simplicity, we had the following characteristics in mind:
\begin{enumerate}
\item 1-to-1 correspondence with gadgets, to ease gadget assignment\footnote{We also note that this eliminates the need for \textit{gadget arrangement}, which was another component of Schwartz, et. al.'s application \textit{Q} \cite{schwartz}.}.  We settle for a mapping between single-string instructions and gadget types recognizable by our gadget classifier (see Section~\ref{sec:classification}).
\item Interleaved instructions and data.  This is pursuant one of our project extensions. We want to be able to:
\begin{enumerate}
\item Specify what data should be at the top of stack when a given gadget is entered.
\item Allow for references (pointers) in our data structures.
\end{enumerate}
\item Straightforward translation of existing shellcode.
\item In the same vein, richness to describe useful payloads.
\end{enumerate}
Out of these requirements was born our regular input language.  An informal syntax is given in Figure~\ref{fig:input_language_syntax}.

\subsection{Introducing gadget blocks}
An input payload is comprised of a sequence of single-line \textit{instructions}, each followed by zero or more \textit{stack items}.  As mentioned, there is a 1-to-1 correspondence between gadget types and instructions.  The data following each instruction indicates what data should be available at the top-of-stack when the instruction's gadget is entered.  Together, an instruction and its stack items form a \textit{gadget block}, which is treated in software, up to a point, as a single unit.  The bottom of Figure~\ref{fig:input_language_syntax} shows two gadget blocks, where the first has the instruction \texttt{EDX:=*ESP\_ESP:=ESP+8\_NOCHANGE:EAX,EBX,ECX}.  This particular block the word \texttt{0x00000000} to be at the top-of-stack when the instruction is entered.

\subsection{Instruction strings}
There is a 1-to-1 relationship between instruction strings and gadget types.  We chose a format for instruction strings which made them as human-readable as possible.  We stress that these strings are \textit{wholly arbitrary} and have no necessary complexity at all.  These strings are not parsed for meaning, but simply mapped to formulae used by our BAP classifier.  The rough format we chose for these instructions was \texttt{ACTION\_STACKOFFSET\_INVARIANTS}\footnote{An opportunity for improvement on our input language is assigning meaning to instruction formatting, so that BAP formulae may be automatically generated.}.  A mapping of instruction strings to instruction semantics on a subset of the instructions we created is shown in Table ~\ref{table:input_language_semantics}.

\subsection{Stack items}
Each gadget block may contain zero or more \textit{stack items}.  There are three types:
\begin{enumerate}
\item \textit{Pointer stack item}: Placeholder for a pointer to an item with a given label.
\item \textit{Offset stack item}: Placeholder for the distance, in bytes, between two labeled items.
\item \textit{Raw stack item}.  Raw data with a desired size ($\leq~4$ bytes) to be placed inline with the payload. (See Section~\ref{sec:endianness} for notes on endian-ness.)
\end{enumerate}

\subsection{Constructing payload descriptions}
An attacker creates a \textit{payload description} by creating a file containing a sequence of gadget blocks.  During payload generation, the contents of these gadget blocks become the \textit{payload proper} (see Section~\ref{sec:resolution}).  Sample payload descriptions are given in Appendix~\ref{appendix:sec:payloads}.

\subsection{Representation in software}
Parsing an input file of this form gives us a sequence of gadget blocks, where each gadget block has an instruction and a variable-length list of stack items.  In software, each gadget block has a fixture\footnote{These are implemented simply as pointers, which are initially assigned \texttt{NULL}.}, where a satisfying gadget is attached.  Initially all fixtures are empty.  This sequence of gadget blocks is passed to \textit{gadget assignment}.

\begin{table*}
\centering
\begin{tabular}{l|l}
\hline
\texttt{EAX:=*ESP\_ESP:=ESP+8}  & Load word at TOS into \texttt{EAX} and increment \texttt{ESP} to next gadget (+8). \\ \hline
\texttt{EAX:=*ESP\_ESP:=ESP+8\_NOCHANGE:EBX} & The same, except preserve the value of \texttt{EBX}. \\ \hline
\texttt{*EAX:=EAX+*EAX\_ESP:=ESP+4} & Add into value pointed to by \texttt{EAX} the value of \texttt{EAX} itself and increment ESP. \\ \hline
\texttt{INT0x80\_ESP:=ESP+4} & Perform software interrupt \texttt{0x80} and increment \texttt{ESP} to the next gadget. \\ \hline
\end{tabular}
\caption{Semantics for a small handful of the instruction strings we created.}
\label{table:input_language_semantics}
\end{table*}

\begin{figure}
\centering
\begin{Verbatim}[frame=lines]
[Label]|Instruction  ; comment
[Label]|Size (0xdeadbeef | Label)  ; comment
[Label]|...
\end{Verbatim}
\begin{Verbatim}[frame=lines]
EDX:=*ESP_ESP:=ESP+8_NOCHANGE:EAX,EBX,ECX
4 0x0
INT0x80_ESP:=ESP+4_NOCHANGE:EAX,EBX,ECX
B|4 A
4 0x0
A|4 0x2f62696e
4 0x2f2f7368
4 0x0
\end{Verbatim}
\caption{Top: Informal input language syntax.  The top line is an instruction with an optional label.  Data to be at the top-of-stack when the instruction's gadget is entered are listed beneath.  Specifying a label as data in a stack item creates a pointer.  An instruction combined with its stack items forms a \textit{gadget block}. Below: A sample snippet from our \texttt{execve() /bin/sh} payload (see Section ~\ref{sec:payloads}).  The field labeled \texttt{B} is the \texttt{char *argv[]} array for \texttt{/bin/sh}, and the field labeled \texttt{A} is the string \texttt{"/bin/sh"}.}
\label{fig:input_language_syntax}
\end{figure}

\subsection{Note on endian-ness}
\label{sec:endianness}
The data in the final payload string is directly interpreted by the victim machine's architecture, which makes endian-ness a concern.  In the payload description, we must specify \textit{exactly what we want on the stack, and in that byte-order}.  For example, if we wish the string \texttt{"/bin//sh"} on the stack, we first give the word \texttt{0x2f62696e} (\texttt{"/bin"}), and then \texttt{0x2f2f7368} (\texttt{"//sh"}).  If we wish the \textit{value} \texttt{5} (as a 4-byte word) on the stack and we are attacking a little-endian machine, we give the little-endian form \texttt{0x05000000}.  In general, the first byte of a word in the input payload is the one occupying the lowest address in the loaded payload.
